// poj3463
// 题意：给定n(<=1000)个点，m(<=10000)条有向边，设从起点s到终点t
//       的最短路长度为dis，现在问从s到t的长度为dis或dis+1的路的
//       条数。
//
// 题解：dis+1肯定是次短路，所以这题可以转为求最短路和次短路的条数
//       和，这可以在dijkstra过程中分别维护两个dist来完成。
//
//       不过这题也有个别的思路，就是统计s到每一个点的最短路，以及
//       每个点到t的最短路（反向图），然后枚举每一条长度加1的边比如
//       u->v，要确保是这条边增加1, 只需要保证u是在最短路上的点，
//       因为次短路肯定是由一段最短路+后一段次短路产生，u相当于这其中
//       的分界点，我们需要保证前面一定是最短的(另外只枚举u也不会
//       重复，因为如果这条路后面的边u'->v'再被枚举到，如果u'在最短上，
//       那么dist[u']肯定不是原来那条路的，如果不在那u'就会被跳过)。
//       然后如果u->v的费用恰为应该最短的费用+1就把两边计数乘起来
//       加上去就行。
//
// run: $exec < input
// opt: 0
// flag: -g
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>

struct edge
{
	edge(int to, int cost) : to(to), cost(cost) {}
	edge() {}
	int to, cost;
};

int const inf = 1 << 30;
int const maxn = 1007;
long long f[maxn][2];
int n, m, s, t;

std::vector<edge> graph[2][maxn];
typedef std::vector<edge>::iterator edge_iter;

void add_edge(int u, int v, int cost)
{
	graph[0][u].push_back(edge(v, cost));
	graph[1][v].push_back(edge(u, cost));
}

int dijkstra_count(int source, int target)
{
	typedef std::pair<int, int> cost_end;
	std::vector<int> dist[2];
	for (int i = 0; i < 2; i++) {
		dist[i].resize(n + 1);
		std::fill(dist[i].begin(), dist[i].end(), inf);
		int t = !i ? source : target;
		dist[i][t] = 0;
		f[t][i] = 1;
		std::priority_queue<cost_end, std::vector<cost_end>, std::greater<cost_end> > pq;
		pq.push(std::make_pair(0, t));
		while (!pq.empty()) {
			cost_end tmp = pq.top(); pq.pop();
			int u = tmp.second;
			if (dist[i][u] < tmp.first) continue;

			for (edge_iter e = graph[i][u].begin(); e != graph[i][u].end(); ++e) {
				int v = e->to, c = e->cost;
				if (dist[i][v] > dist[i][u] + c) {
					dist[i][v] = dist[i][u] + c;
					pq.push(std::make_pair(dist[i][v], v));
					f[v][i] = f[u][i];  // 这两个涉及f的地方就是统计更新
				} else if (dist[i][v] == dist[i][u] + c)
					f[v][i] += f[u][i]; // 到当前最短路的个数。
			}
		}
	}

	int min = dist[0][target], ret = f[target][0];
//	std::cerr << min << " " << ret << '\n';
	for (int i = 0; i < n; i++) {
		if (dist[0][i] + dist[1][i] != min) continue;
		for (edge_iter it = graph[0][i].begin(); it != graph[0][i].end(); ++it) {
			int v = it->to, c = it->cost;
			int tmp = dist[0][i] + dist[1][v] + c;
			if (tmp == min + 1) ret += f[i][0] * f[v][1];
		}
	}

	return ret;
}

void init()
{
	std::memset(f, 0, sizeof(f));
	for (int i = 0; i < maxn; i++) {
		graph[0][i].clear();
		graph[1][i].clear();
	}
}

int main()
{
	std::ios::sync_with_stdio(false);
	int T; std::cin >> T;
	while (T--) {
		std::cin >> n >> m;
		init();
		for (int i = 0, x, y, z; i < m; i++) {
			std::cin >> x >> y >> z;
			x--; y--;
			add_edge(x, y, z);
		}
		std::cin >> s >> t;
		std::cout << dijkstra_count(--s, --t) << '\n';
	}
}

